#!/usr/bin/python
# Filename: AdvLinearDS.py

# Advanced Linear Data Structure:
# Matrix, Generalized List

# Matrix
# 1) n dimension matrix a[D1][D2]...[Dn]:
# a[k1][k2]...[kn] unit's address is (k1-1)*(D2*...*Dn) + (k2-1)*(D3*...*Dn) + ... + kn-1
# 2) triangle matrix:
# a) upper triangle matrix a[(1+n)*n/2], m[i][j]'s address is (n+(n-(i-1)))*i/2+j-i
# b) lower triangle matrix a[(1+n)*n/2], m[i][j]'s address is (1+i)*i/2+j
# 3) symmetry matrix:
# a[(1+n)*n/2], m[i][j] = m[j][i] = (1+i)*i/2+j(i>=j)
# 4) diagonal matrix:
# take 3-diagonal matrix as example
# a) i = 0, m[i][j] = j
# b) 0 < i < n, m[i][j] = 2 + 3*(i-1) + j-(i-1)
# 5) spare matrix(load factor <= 0.05):
# use <i, j, value> to present an element of the matrix
# a) cross linked list
# b) matrix multiplication(m*p and p*n) time complexity decrease to (ta+tb)*m*n(ta and tb are max element counts in rows and lines)

# Generalize List
# each sub-list(pair of parenthesis) has a header in diagram presentation
# this header is different to list header
# !!!list header is first element, list tail is a list of all other element besides list header
# 1) pure list(tree): every element(atom or sub-list) can only appears once
# 2) re-enterable list:
# a) atom and sub-list can appear several times, use tag to mark sub-list. eg(L1:(a,b), (c, (L1, d)))
# a.1) ???can atom appear several times alone?
# b) there's no loop, it's a DAG
# 3) cyclic list
# graph >= cyclic list >= re-enterable list(DAG) >= pure list(tree) >= linear list
# 4) storage:
# a) parenthesis string
# b) list and sub-list with(better for insert and delete)/without header
# 5) traversal:
# a) use recursive to traverse
# b) use PH to stop infinite loop
# c) clear PH after traversal

# Memory Management
